package compiler.tac;

import java.util.ArrayList;

import compiler.tac.Instruction.Operator;

public class SSAPRE {
	//ArrayList<SimpleExpt> worklist;
	
	ArrayList<SimpleExpt> worklist = new ArrayList<SimpleExpt>();//expt will be processed
	ArrayList<BasicBlock> bigphiList = new ArrayList<BasicBlock>(); //blocks which contains Bigphi
	
	ArrayList<Boolean> downsafe = new ArrayList<Boolean>(); 
	ArrayList<Boolean> canbeavail = new ArrayList<Boolean>();
	ArrayList<Boolean> willbeavail=new ArrayList<Boolean>();
	ArrayList<Boolean> later = new ArrayList<Boolean>();
	ThreeAddressCode tac;
	int versioncount;
	ArrayList<Instruction> availdef = new ArrayList<Instruction>();
	ArrayList<BasicBlock> availdeflocation = new ArrayList<BasicBlock>();
	ArrayList<Boolean> extraneous = new ArrayList<Boolean>();
	
	
	public void addEmptyBlock()
	{
		ArrayList<BasicBlock> allblocks = tac.getAllBlocks();
		if(allblocks!=null)
			for(int i = 0; i < allblocks.size(); i ++)
			{
				if(allblocks.get(i).getPreds().size() > 1 && allblocks.get(i).getSuccs().size() > 1)
					allblocks.get(i).addPreEmptBlock(tac);
			}
	}
	
	public void InitWorklist()
	{
		ArrayList<BasicBlock> allblocks = tac.getAllBlocks();
		if(allblocks != null)
			for(BasicBlock basicBlock : allblocks)
			{
				ArrayList<Instruction> code = basicBlock.getInstructions();
				if(code!=null)
					for(Instruction inst : code)
					{
						if(inst.oprt == Operator.Add || inst.oprt == Operator.Sub || 
						   inst.oprt == Operator.Mul || inst.oprt == Operator.Div)
						{
							if((tac.getST().isValid(SimpleExpt.cutName(inst.oprdl.getId())) || inst.oprdl.getId().substring(0, 2).equals("$E")) &&
							   (tac.getST().isValid(SimpleExpt.cutName(inst.oprdr.getId())) || inst.oprdr.getId().substring(0, 2).equals("$E")))
							{
								SimpleExpt newExpt = new SimpleExpt(inst.oprt,inst.oprdl.getId(), inst.oprdr.getId());
								
								if(worklist.size()==0 || !isExist(newExpt))
								{
									worklist.add(newExpt);
									//System.out.println("no found expt " + newExpt.toString());	
								}
								inst.exptVersion = newExpt.toString();
							}
						}
						else if(inst.oprt == Operator.Cmp)
						{
							if((tac.getST().isValid(SimpleExpt.cutName(inst.oprdl.getId())) || inst.oprdl.getId().substring(0, 2).equals("$E")) &&
							   (tac.getST().isValid(SimpleExpt.cutName(inst.oprdr.getId())) || inst.oprdr.getId().substring(0, 2).equals("$E")))
							{
								SimpleExpt newExpt = new SimpleExpt(code.get(code.indexOf(inst)+1).oprt,
																	inst.oprdl.getId(), inst.oprdr.getId());
								if(worklist.size()==0 || !isExist(newExpt))
								{
									worklist.add(newExpt);
									//System.out.println("no found expt " + newExpt.toString());
								}
								inst.exptVersion = newExpt.toString();
							}
						}
					}
					
			}	
		//System.out.println("expt number :" + worklist.size());
	}
	
	public void InsertBigPhi(SimpleExpt expt)
	{
		
		ArrayList<BasicBlock> workList = new ArrayList<BasicBlock>();
		ArrayList<Boolean> handled = new ArrayList<Boolean>();
		ArrayList<Boolean> inlist = new ArrayList<Boolean>();
		
		for(int i = 0; i < tac.getAllBlocks().size(); i ++)
		{
			handled.add(false);
			inlist.add(false);
		}
		for(int i = 0; i < tac.getAllBlocks().size(); i ++)
		{
			if(tac.getAllBlocks().get(i).containPhitoE(expt) || tac.getAllBlocks().get(i).containOccrencetoE(expt))
			{
				inlist.set(i, true);
				workList.add(tac.getAllBlocks().get(i));
			}
		}
		
		while(workList.size()>0)
		{
			BasicBlock b = workList.get(0);
			if(b.containPhitoE(expt) && !b.containBigPhitoE(expt))
			{
				b.addBigPhiInstruction(expt, b.getPreds().size());
				bigphiList.add(b);
			}
			if(b.containOccrencetoE(expt) && !b.containBigPhitoE(expt))
				for(BasicBlock df: b.getDomF())
				{
					//not in the worklist
					if(!inlist.get(tac.getAllBlocks().indexOf(df)))
					{
						workList.add(df);
						inlist.set(tac.getAllBlocks().indexOf(df),true);
						handled.set(tac.getAllBlocks().indexOf(df), false);
					}
					if(!df.containBigPhitoE(expt))
					{
						df.addBigPhiInstruction(expt, df.getPreds().size());
						bigphiList.add(df);
						//System.out.println("add Phi for " + expt.toString() + " in block" + df.getOrder());
						handled.set(tac.getAllBlocks().indexOf(df), false);
					}	
					//if(work)
				}
			workList.remove(0);
		}
		
	}
	
	public void rename(SimpleExpt expt)
	{
		ExptNameStack stack = new ExptNameStack();
		stack = tac.getEntry().renameE(expt, stack);
		versioncount = stack.count;
	}
	
	public void DownSafe(SimpleExpt expt)
	{
		for(int i = 0; i < bigphiList.size(); i ++)
		{
			downsafe.add(true);
		}
		BasicBlock exit = tac.getExit();
		initdownsafe(exit, expt);
	}
	
	public void initdownsafe(BasicBlock b, SimpleExpt expt)
	{
		if(b.getPreds()!=null && b.getPreds().size()>0)
			for(BasicBlock pre: b.getPreds())
			{
				if(!pre.containOccrencetoE(expt))
				{
					//System.out.println("now in block "+b.getOrder() + "and not contain");
					if(pre.containBigPhitoE(expt))
					{
						downsafe.set(bigphiList.indexOf(pre), false);
						//System.out.println("block set to unsafe " + pre.getOrder());
						initdownsafe(pre, expt);
					}
					else {
						initdownsafe(pre, expt);
					}
				}
			}
	}
	
	public void WillBeAvail(SimpleExpt expt)
	{
		calhasrealuse(expt);
		calcanbeavail(expt);
		callater(expt);
		for(int i = 0;i < bigphiList.size(); i ++)
		{
			willbeavail.add(canbeavail.get(i)&&!later.get(i));
		}
	}
	
	public void calcanbeavail(SimpleExpt expt)
	{
		for(int i = 0; i < bigphiList.size(); i ++)
			canbeavail.add(true);
		for(int i =0; i < bigphiList.size(); i ++)
		{
			Instruction inst = bigphiList.get(i).getBigPhiInstruction(expt);
			if(!downsafe.get(i) && canbeavail.get(i))
			{
				if(inst.containPhiArgVersion(-1))
					resetcanbeavail(bigphiList.get(i),expt);
			}
		}
	}
	
	public void resetcanbeavail(BasicBlock b, SimpleExpt expt)
	{
		//System.out.println("reset canbeavail of block " + b.getOrder());
		canbeavail.set(bigphiList.indexOf(b), false);
		int version = SimpleExpt.getVersion(b.getBigPhiInstruction(expt).dest.getId());
		
		for(BasicBlock block: bigphiList)
		{
			Instruction inst=block.getBigPhiInstruction(expt);
			int position = inst.versionPosition(version);
			if(position !=-1 && !inst.hasrealuse.get(position))
			{
				if(!downsafe.get(bigphiList.indexOf(block)) && canbeavail.get(bigphiList.indexOf(block)))
					resetcanbeavail(block, expt);
			}
		}
	}
	
	public void resetlater(BasicBlock b, SimpleExpt expt)
	{
		//System.out.println("reset later of block " + b.getOrder());
		later.set(bigphiList.indexOf(b), false);
		int version = SimpleExpt.getVersion(b.getBigPhiInstruction(expt).dest.getId());
		
		for(BasicBlock block: bigphiList)
		{
			Instruction inst=block.getBigPhiInstruction(expt);
			int position = inst.versionPosition(version);
			if(position !=-1)
			{
				if(later.get(bigphiList.indexOf(block)))
					resetlater(block, expt);
			}
		}
	}
	public void callater(SimpleExpt expt)
	{
		for(int i = 0; i < canbeavail.size(); i ++)
			later.add(canbeavail.get(i));
		//System.out.println("later size " + later.size());
		for(int i = 0; i < bigphiList.size(); i ++)
		{
			Instruction inst= bigphiList.get(i).getBigPhiInstruction(expt);
			
			//System.out.println(i + inst.toString());
			if(later.get(i) && inst.isLater())
				resetlater(bigphiList.get(i), expt);
		}
	}
	
	public void finalize1(SimpleExpt expt)
	{
		for(int i = 0; i <= versioncount; i ++)
		{
			availdef.add(null);
			availdeflocation.add(null);
		}
		dofinal(tac.getEntry(),expt);
	}
	
	public void finalize2(SimpleExpt expt)
	{
		extraneous.addAll(willbeavail);
		for(BasicBlock b: tac.getAllBlocks())
		{
			if(b.containOccrencetoE(expt) || b.containBigPhitoE(expt))	
			{
				for(Instruction inst: b.getInstructions())
				{
					if(inst.exptVersion !=null && SimpleExpt.cutName(inst.exptVersion).equals(expt.toString()) && 
							   SimpleExpt.getVersion(inst.exptVersion)!=-1)
					{
						inst.save = false;
						if(inst.reload)
							set_save(inst.def.get(0),expt);
					}
				}
			}
		}
		for(BasicBlock b: tac.getAllBlocks())
		{
			if(b.containOccrencetoE(expt) || b.containBigPhitoE(expt))	
			{
				for(Instruction inst: b.getInstructions())
				{
					if(inst.exptVersion !=null &&SimpleExpt.cutName(inst.exptVersion).equals(expt.toString()) && 
					   SimpleExpt.getVersion(inst.exptVersion)!=-1)
					{
						if(inst.reload)
							set_save(inst.def.get(0),expt);
					}
				}
			}
		}
		
		for(int i = 0; i < bigphiList.size(); i ++)
		{
			Instruction bigphi = bigphiList.get(i).getBigPhiInstruction(expt);
			if(willbeavail.get(i))
			{
				if(extraneous.get(i))
				{
					for(int j = 0; j < bigphi.phiArg.size(); j ++)
					{
						Instruction defInstruction= bigphi.def.get(j);
						if(defInstruction.exptVersion!=null)
							if(SimpleExpt.cutName(defInstruction.exptVersion).equals(expt.toString()))
								set_replacement(bigphi, defInstruction,expt);
						if(defInstruction.oprt== Operator.BigPhi && !extraneous.get(getIndexofPhi(defInstruction,expt)))
							set_replacement(bigphi, defInstruction,expt);
					}
				}
			}	
			else {
				bigphiList.remove(i);
				willbeavail.remove(i);
				extraneous.remove(i);
			}
		}
		
	}
	public void set_save(Instruction inst, SimpleExpt expt)
	{
		if(inst.exptVersion!=null && SimpleExpt.getVersion(inst.exptVersion)!=-1)
			inst.save=true;
		else if(inst.oprt==Operator.BigPhi)
		{
			for(int i = 0; i < inst.phiArg.size(); i++)
				if(!inst.processed.get(i))
					set_save(inst.def.get(i),expt);
		}
		
		if(inst.exptVersion!=null)
		{
			BasicBlock location = bigphiList.get(getIndexofPhi(inst, expt));
			for(BasicBlock df: location.domChildren)
			{
				if(bigphiList.indexOf(df)!=-1)
				{
					if(willbeavail.get(bigphiList.indexOf(df)))
						extraneous.set(bigphiList.indexOf(df),false);
				}
			}
		}
	}
	
	public void set_replacement(Instruction use, Instruction def, SimpleExpt expt)
	{
		for(BasicBlock fiBlock: bigphiList)
		{
			Instruction bigphi=fiBlock.getBigPhiInstruction(expt);
			
			for(Instruction defInstruction: bigphi.def)
				if(defInstruction == use )
					if(extraneous.get(bigphiList.indexOf(fiBlock)))
						set_replacement(bigphi, def, expt);
					else {
						bigphi.phiArg.set(bigphi.def.indexOf(defInstruction),new Address(def.dest.getId()));
						//bigphi.def.set(bigphi.def.indexOf(defInstruction), def);
					}
		}
		for(BasicBlock b: tac.getAllBlocks())
		{
			if(b.containOccrencetoE(expt) || b.containBigPhitoE(expt))	
			{
				for(Instruction inst: b.getInstructions())
				{
					if(SimpleExpt.cutName(inst.exptVersion).equals(expt.toString()) && 
							   SimpleExpt.getVersion(inst.exptVersion)!=-1)
					{
						if(inst.reload && inst.def.get(0)==use)
							inst.def.set(0, def);
					}
				}
			}
		}
		
		int index = getIndexofPhi(use, expt);
		bigphiList.remove(index);
		extraneous.remove(index);
		willbeavail.remove(index);
	}
	
	public int getIndexofPhi(Instruction i,SimpleExpt expt)
	{
		for(BasicBlock b: bigphiList)
		{
			if(b.getBigPhiInstruction(expt)==i)
				return bigphiList.indexOf(b);
		}
		return -1;
	}
	public void dofinal(BasicBlock b, SimpleExpt expt)
	{
		if(b.containOccrencetoE(expt) || b.containBigPhitoE(expt))
		{
			for(Instruction inst: b.getInstructions())
			{
				if(inst.isOccurence(expt))
				{
					int version;
					if(inst.oprt == Operator.BigPhi)
					{
						version=SimpleExpt.getVersion(inst.dest.getId());
					    calinsert(inst);
						if(willbeavail.get(bigphiList.indexOf(b)))
						{
							availdef.set(version, inst);
							availdeflocation.set(version, b);
						}
						
						if(willbeavail.get(bigphiList.indexOf(b)))
						{
							calinsert(inst);
							for(int i = 0; i < inst.phiArg.size(); i ++)
							{
								if(inst.insert.get(i))
								{
									Instruction inserted = b.getPreds().get(i).insert(expt);
									inst.def.set(i, inserted);
								}
								else {
									inst.def.set(i, availdef.get(version));
								}
							}
						}	

					}
					else {
						version = SimpleExpt.getVersion(inst.exptVersion);
						if(availdef.get(version)==null || availdeflocation.get(version).getDomChildren().indexOf(b)==-1)
						{
							inst.reload=false;
							availdef.set(version, inst);
							availdeflocation.set(version, b);
						}
						else {
							inst.reload = true;
							inst.def = new ArrayList<Instruction>();
							if(inst.def!=null && inst.def.size()>0)
								inst.def.set(0, availdef.get(version));
							else {
								inst.def.add(availdef.get(version));
							}
						}
							
					}
				}
			}
		}
		for(BasicBlock child: b.getDomChildren())
			dofinal(child, expt);
	}
	public void calinsert(Instruction inst)
	{
		if(inst.phiArg!=null)
			for(int i = 0; i < inst.phiArg.size(); i ++)
			{
				if(SimpleExpt.getVersion(inst.phiArg.get(i).getId())==-1)
					inst.insert.set(i, true);
				else if(!inst.hasrealuse.get(i) && inst.def.get(i).oprt==Operator.BigPhi && willbeavail.get(bigphiList.indexOf(inst.def.get(i))))
					inst.insert.set(i, true);
			}
	}
	
	
	public void doSSAPRE(ThreeAddressCode tac)
	{
		this.tac=tac;
		if(tac.getChildren()!=null)
			for(ThreeAddressCode child : tac.getChildren())
			{
				SSAPRE ssapre = new SSAPRE();
				ssapre.doSSAPRE(child);
			}
		
		InitWorklist();
		ArrayList<SimpleExpt> wList= new ArrayList<SimpleExpt>();
		wList.addAll(worklist);
		
		//System.out.println("wlist number "+ wList.size());
		while(wList.size()>0)
		{
			init();
			//System.out.println("handle the expt of "+ wList.get(0).toString());
			InsertBigPhi(wList.get(0));
			rename(wList.get(0));
			DownSafe(wList.get(0));
			WillBeAvail(wList.get(0));
			finalize1(wList.get(0));
			//finalize2(wList.get(0));
			wList.remove(0);
		}
	}
	
	public void init()
	{
		bigphiList = new ArrayList<BasicBlock>(); //blocks which contains Bigphi
		
		downsafe = new ArrayList<Boolean>(); 
		canbeavail = new ArrayList<Boolean>();
		willbeavail=new ArrayList<Boolean>();
		later = new ArrayList<Boolean>();
		//this.tac = null;
		versioncount = 0;
		availdef = new ArrayList<Instruction>();
		availdeflocation = new ArrayList<BasicBlock>();
		extraneous = new ArrayList<Boolean>();
		
		//reload = new ArrayList<Boolean>();
	}
	public void calhasrealuse(SimpleExpt expt)
	{
		if(bigphiList!=null && bigphiList.size()>0)
			for(BasicBlock block: bigphiList)
			{
				Instruction inst = block.getBigPhiInstruction(expt);
				for(Address add: inst.phiArg)
				{
					if(SimpleExpt.getVersion(add.getId())!=-1)
					{
						boolean occur = false;
						for(BasicBlock pre: block.getPreds())
							if(pre.calhasrealuse(expt,SimpleExpt.getVersion(add.getId())))
							{
								occur = true;
								break;
							}
						
						inst.hasrealuse.set(inst.phiArg.indexOf(add), occur);
						//System.out.println("set hasrealuse of block " + block.getOrder() + inst.phiArg.indexOf(add)
						//		+ "th arg as " + occur);
						
					}			
				}
			}	
	}
	boolean isExist(SimpleExpt e)
	{
		int i;
		for(i = 0; i < worklist.size(); i ++)
			if(worklist.get(i).equals(e))
				return true;
		return false;
	}
}
